import sun.reflect.generics.tree.Tree;


import java.util.*;

public class BinaryTree {
    static class TreeNode{
        public char val ;
        public TreeNode left ;
        public TreeNode right ;

        public TreeNode(char val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    '}';
        }
    }
    public TreeNode createTree() {    //创造一个二叉树
        TreeNode node1 = new TreeNode('A');
        TreeNode node2 = new TreeNode('B');
        TreeNode node3 = new TreeNode('C');
        TreeNode node4 = new TreeNode('D');
        TreeNode node5 = new TreeNode('E');
        TreeNode node6 = new TreeNode('F');
        TreeNode node7 = new TreeNode('G');
        TreeNode node8 = new TreeNode('H');
        node1.left = node2 ;
        node1.right = node3 ;
        node2.left = node4 ;
        node2.right = node5 ;
        node3.left = node6 ;
        node3.right = node7 ;
        node4.left = node8;
        return  node1 ;
    }

    //求两个指定结点的最近的公共祖先结点
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null ;
        }
        if(root == p || root == q){
            return root ;
        }
        TreeNode leftTree = lowestCommonAncestor(root.left, p ,q);
        TreeNode rightTree = lowestCommonAncestor(root.right ,p ,q);
        if(leftTree!=null && rightTree!=null){
            return root ;
        }else if(leftTree != null){
            return leftTree;
        }else{
            return rightTree;
        }
    }

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null ;
        Stack<TreeNode> stackP = new Stack<>() ;
        Stack<TreeNode> stackQ = new Stack<>() ;
        getPath(root , p , stackP);
        getPath(root , q , stackQ) ;
        int pSize = stackP.size() ;
        int qSize = stackQ.size();
        if(pSize > qSize){
            while(pSize > qSize){
                stackP.pop() ;
                pSize -- ;
            }
        }else{
            while(pSize < qSize){
                stackQ.pop() ;
                qSize -- ;
            }
        }
        while(!stackP.isEmpty()){
            if(stackP.peek().equals(stackQ.peek())){
                return stackP.peek() ;
            }
            stackP.pop();
            stackQ.pop() ;
        }
        return null ;
    }
    //获取路线，将经过的结点放到栈里去
    private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
        if(root == null || node == null){
            return false ;
        }
        stack.push(root);
    if(root == node){
        return true ;
    }
    boolean leftFlg =  getPath(root.left , node,stack);
    if(leftFlg){
        return true ;
    }
    boolean rightFlg =  getPath(root.right , node,stack);
        if(rightFlg){
            return true ;
        }
    stack.pop() ;
   return false;
    }


}
